package com.wfm.leetcode.editor.cn;

import com.wfm.common.ArrayUtils;
import java.util.Arrays;

public class PThree00最长递增子序列{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length==1) return 1;
        int[] dp = new int[nums.length];
        int ans = 0;
        Arrays.fill(dp,1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = i-1; j >=0 ; j--) {
                if(nums[j]<nums[i]){
                    dp[i]=Math.max(dp[j]+1,dp[i]);
                }
            }
            ans = Math.max(ans,dp[i]);
        }
        System.out.println(Arrays.toString(dp));
        return ans;

    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PThree00最长递增子序列().new Solution();
        int i = solution.lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18});
        System.out.println(i);
    }
}